1. FIELD OF THE INVENTION
The present invention relates to the field of systems for distributed computing, communication and control and, more specifically, to the area of communication of information between devices in a distributed computing environment.
2. DESCRIPTION OF THE RELATED ART
There are a large number of networks known in the art which networks allow for communication of messages between nodes that make up the networks. In such networks, a node may transmit a message (referred to herein alternatively as the "transmitting node", the "origin node", or the "source node"). The message may be received by another node (where the other node is not the intended final destination node of the message). This node will be referred to herein as an "intermediate node" and, sometimes, more specifically, is referred to as a "router node". The intermediate node then retransmits the message. This process of receiving and retransmitting the message may continue through one or more additional intermediate nodes until, finally, the message reaches the final intended destination node or nodes (referred to herein as the "destination node").
Of course, in such a system, designs must provide for retransmission of the message until it reaches the desired destination node(s). However, it is important in such designs that the message is not repeatably retransmitted throughout the network after the message is finally received by the destination node(s) because such retransmission will increase, unnecessarily, traffic on the network. In fact, as will be seen, in certain scenarios, it is possible for such retransmission to continue infinitely until the network is reset.
The present invention offers an improved method of communicating messages between nodes in such a network which provides for reduced unnecessary retransmission of messages from node-to-node within the network. In order to describe problems solved by the present invention, it may be useful to refer to FIG. 1.
In FIG. 1, a network is illustrated having 18 nodes referred to with reference numerals 110-128. In this network, nodes 110-114 are members of subnet 1 102 of domain 1 131. Nodes 116-119 are members of subnet 2 103 of domain 1 131. Nodes 120-124 are members of subnet 2 103 of domain 2 132 and nodes 125-128 are members of subnet 1 104 of domain 2 132. Nodes 114, 116, 119, 122, and 125 are each router nodes which provide for routing of messages between nodes in different subnets. As will be explained in greater detail below, nodes may include in transmitted messages their node id (source node id), subnet (source subnet), and domain (source domain) and, in the case of group messages, a destination group id.
It is first useful to assume for a first example that nodes 110, 111 and 118 are each members of the same group (i.e., group 1). FIG. 2(a) illustrates a prior art method of transmitting a group message from node 110 to other nodes in the group (e.g., nodes 111 and 118). Initially, node 110 may format a message and transmit on media 161, block 201. The message is received and processed by node 111, block 202. (Nodes 112 and 113 may also sense the message but reject it because it is addresses a group 1.) Node 114 also receives the message, block 203. Node 114 is a router node and, therefore, accepts the message even though it is not a member of the group designated by the message. Node 114 then transmits the message, for example, by RF signals, block 114. In the described network, the message should be received by node 119, block 206 so that it might be retransmitted on media 155 for reception by node 118 (the third node in group 1). As illustrated, the message is received by node 119, block 206, and is retransmitted on power line 155, block 208, so that it is received by node 118, block 210. (The message retransmitted by node 119 is also received by node 116 which may retransmit the message. This will be explained in greater detail below. In addition, the message is received by node 117, however, because this node is not in group 1, the message is ignored. Finally, the message is received by nodes 125-28 which also ignore the message because these nodes are not members of domain 1 131.)
Importantly, the message retransmitted from node 114 may also be received by node 116, block 205 (and by nodes 122 and 125, block 207). If received by node 116, the message will be retransmitted on power line 155 by node 116, block 209. It will be again received by node 118 (and preferably ignored as a duplicate) as well be being received by nodes 117 and 126-128. However, it will also be received by node 119, block 211, which will retransmit the message, block 212. The message, retransmitted by node 119 may again be received by node 116 and a seemingly infinite loop is then created. (Of course, the message may also be rereceived by node 114, creating similar problems.) If the message is received by nodes 122 or 125, it will be ignored because nodes 122 and 125 are not members of domain 1 131.
Many networked computing systems have avoided dealing with the above-described problem. For example, certain networks only allow transmission over wire media. This provides for control over recipients of messages. Other systems implement a "hop count" which is transmitted with the message. Each time the message is received by a router node, the hop count is incremented and, when it exceeds a predetermined maximum, the message is no longer retransmitted by the router nodes. Of course, neither of these solutions is ideal.
Therefore, what is required is a system in which messages are retransmitted in such a manner that the message is received by each intended recipient but also such that unnecessary retransmission of the message is not required. Such a system should be media independent.
A second class of problems may also be described with reference to FIG. 1 and, now, with reference to FIG. 2(b). Assume in this example, that node 110 is unconfigured (an "unconfigured node" as that term is used herein has not yet been assigned a domain and subnet address and is therefore unable to transmit source domain and subnet information with messages). In the system of the preferred embodiment, node 110 may format and broadcast a message before it has been configured-for example, node 110 may be requested to transmit its node id onto the network. However, without source domain or source subnet address information, there is no information in the packet to tell the routers how to route the packet.
In the preferred embodiment, node 110 may be requested to transmit its node id by activating a "service pin" which is a hardware pin on node 110 specially designated to cause transmission of a message which broadcasts the node's node id. It is worthwhile to briefly note that in the system of the preferred embodiment, all nodes are assigned unique 48-bit node ids at the time of their manufacture; therefore, even an unconfigured node has a node id. This assignment of unique 48-bit node ids is better described with reference to U.S. Pat. No. 4,918,690 Markkula Jr. et al. titled "Network and Intelligent Cell for Providing Sensing, Bidirectional Communications and Control" which patent is assigned to the assignee of the present invention.
The message broadcast by node 110 is received by nodes 111 and 112, block 222. The message is also received by node 114, block 223, and retransmitted, block 224. The message may then be received by any or all of nodes 119, block 226, node 116, block 225, or nodes 122 and 125, block 227. Whether or not each of these nodes received the transmitted message depends on a number of factors including the strength of the signal transmitted by node 114 and the capability of each of nodes 119, 122 and 125 to receive messages. However, the networked computing system should be designed to operate properly in the event any of these nodes receives the message.
The example of FIG. 2(b) illustrates further detail of the communication process after the message is received by nodes 119 and 116. In the case of a message received by node 119, block 226, node 119 may retransmit the message on power line 155, block 228, and it will be received by nodes 116-118 and 125-128, block 230. Node 116 may then retransmit the message, block 233 and it may then be again received by node 119 (among other possible nodes). This, of course, creates a potentially infinite loop of retransmission. The message being received by node 116, block 225, creates similar problems wherein node 116 retransmits on power line 155 and node 119 (among others) receives the message, block 231, and retransmits, block 232, again creating a potentially infinite loop. (It might be noted that preferably nodes 125-128 will ignore the message because they are not members of the proper domain).
Again, what is desired is to develop a system in which unnecessary retransmission of messages (and especially potentially infinite loops) are reduced, avoided or eliminated.
These and other objects of the present invention will be better understood with reference to the Detailed Description of the Preferred Embodiment, the accompanying drawings, and the claims.